前中後運算式轉置

中置運算式是人腦的計算中最直觀且最習慣理解的表示式，會將運算子(EX:加號)放在兩個運算元中間，然而這並不是電腦對運算式的處理方式，電腦會消除括號，並將運算子放在運算元的前後，分別稱為前置運算式與後置運算式，以下便是將中置的運算式處理為電腦所熟悉的表示法。

中轉前序

程式說明

相關函式

reverse():將特定字串反轉

說明:
將存入字串做反轉的處理。

void reverse(char str[MAX]) {
  int i, j;
  char c;
  for (i = 0, j = strlen(str) - 1; i < j; ++i, --j)
    c = str[i], str[i] = str[j], str[j] = c;
}

compare():判別運算子並回傳優先度

說明:
利用switch來判斷引入字元，並回傳其優先度。

int compare(char op) {
  switch (op) {
  case '+':
  case '-':
    return 1;
  case '*':
  case '/':
  case '%':
    return 2;
  default:
    return 0;
  }
}

Prefix():帶入原中置運算式，並生成前置運算式

說明:
原運算式會經過轉換，並存入新的陣列中，原運算式經過倒經過倒的順序，
會生成與結果運算式相反的字串。

void Prefix(char *str, char *new_str) {
  char stack[MAX];
  int top = 0, j = 0, i;
  for (i = strlen(str) - 1; i >= 0; i--) {
    // printf("\n--------%c--------\n", str[i]);
    //由最後一個開始處理到第一個字元
    switch (str[i]) {
    case '+':
    case '-':
    case '*':
    case '/':
    case '%':
      while (compare(str[i]) < compare(stack[top])) {
        new_str[j++] = stack[top--];
      }
      //遇到運算符號時，先在while迴圈中利用compare判斷優先度，
      //將stack堆疊中大於目前運算子優先度提出
      stack[++top] = str[i];
      //存入當前運算子到stack堆疊中
      continue;
    case ')':
      stack[++top] = str[i];
      continue;
      //因為是倒著輸出，因此在合法的運算式中會最先遇到')'，
      //一樣將')'存入堆疊，等待'('出現
    case '(':
      while (stack[top] != ')') {
        new_str[j++] = stack[top--];
      }
      top--;
      continue;
      //遇到'('時，將堆疊內的運算子全數輸出，直到遇見')'
    default:
      new_str[j++] = str[i];
      continue;
      //非運算子的字元直接存入新字串
    }
  }
  while (top != 0) {
    new_str[j++] = stack[top--];
  }
}

Infix_to_Prefix():整合中置轉前置之功能

說明:
因為Prefix在處理運算式的過程是倒著處理，所以輸出的結果是相反
的，需要藉由reverse函式，將運算結果倒回來。

void Infix_to_Prefix(char str[]) {
  char new_str[MAX] = {"\0"};
  printf("\n--------------------------\n");
  printf("中置式:%s\n", str);
  Prefix(str, new_str);
  reverse(new_str);
  printf("前置式:%s", new_str);
}

主程式:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#define MAX 20
int main() {
  char str1[MAX] = {"2+3*2/2-2"};
  char str2[MAX] = {"4/2-1+2*3-4*1"};
  //測資1,2
  Infix_to_Prefix(str1);
  Infix_to_Prefix(str2);
  return 0;
}

中轉後序

程式說明

與前序差異

1:

• 前置式:由最後一個字元判斷到第一個字元。
• 後置式:第一個判斷到最後一個。

2:

• 前置式:在判斷取代運算子的時候，是以大於其運算子為依據。
• 後置式:在判斷取代運算子的時候，是以大於且等於其運算子為依據。

3:

• 前置式:因為在引入字元順序式相反的，所以要將')'作為優先存入，並判斷結束的'('。
• 後置式:因為在引入字元的順序是正常的，所以優先存入按照'('後')'的基本法則就好

之後再用看看能不能前後直接互換和轉中置表示法。